/*
 * Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list.
 * It starts by comparing every two elements (i.e. 1 with 2, then 3 with 4...) and swapping them 
 * if the first should come after the second. It then merges each of the resulting lists of two into
 * lists of four, then merges those lists of four, and so on; until at last two lists are merged into 
 * the final sorted list. Of the algorithms described here, this is the first that scales well to 
 * very large lists.
 */

#include <iostream>
#include <algorithm>

using namespace std;

void swap(int &a, int &b){
	int c=a;
	a=b;
	b=c;
}

void print_array(int* a, int n, char* sep=" "){
	for(int i=0;i<n;i++){
		cout<<a[i]<<sep;
	}
	cout <<endl;
}

void mergesort(int a[],int n){
	if(n==1) return;
	if(n==2){
		if(a[0]>a[1])
			swap(a[0],a[1]);
		return;
	}
	mergesort(a,n/2);
	mergesort(a+n/2,n-n/2);

	//inplace mix two sorted array
  // this is time-consuming, it's bad
	for(int i=0,j=n/2;j<n;j++){
		while(a[j]>a[i] && i<j) i++;
		if(i>=n) break;
		int m=a[j];
		for(int k=j;k>i;k--){
			a[k]=a[k-1];
		}
		a[i]=m;
	}
}

int main(){
	int array[]={0,1,2,3,4,5,6,7,8,9};
	int n=sizeof(array)/sizeof(int);
	srand ( time(NULL) );
	random_shuffle(array, array+n);

	cout<<"before\n";
	print_array(array,n);

	mergesort(array,n);

	cout<<"after\n";
	print_array(array,n);
}
